#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

struct ListNode {
	int val;
	struct ListNode* next;
};

//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//	struct ListNode* pcul = NULL;
//	struct ListNode* pphe = NULL;
//	while (list1 && list2)
//	{
//		if (list1->val > list2->val)
//		{
//			if (pcul == NULL)
//			{
//				pphe = pcul = list2;
//			}
//			else
//			{
//				pcul->next = list2;
//				pcul = pcul->next;
//			}
//			list2 = list2->next;
//		}
//		else
//		{
//			if (pcul == NULL)
//			{
//				pphe = pcul = list1;
//			}
//			else
//			{
//				pcul->next = list1;
//				pcul = pcul->next;
//			}
//			list1 = list1->next;
//		}
//	}
//	if (list1)
//	{
//		pcul->next = list1;
//	}
//	if (list2)
//	{
//		pcul->next = list2;
//	}
//	return pphe;
//}
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	ListNode* pcul, * pphe;
	pphe = pcul = (ListNode*)malloc(sizeof(ListNode));
	ListNode* l1 = list1;
	ListNode* l2 = list2;
	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			pcul->next = l1;
			pcul = pcul->next;
			l1 = l1->next;
		}
		else
		{
			pcul->next = l2;
			pcul = pcul->next;
			l2 = l2->next;
		}
	}
	if (l1!=NULL)
	{
		pcul->next = l1;
	}
	if (l2!=NULL)
	{
		pcul->next = l2;
	}
	struct ListNode* l3 = pphe->next;
	free(pphe);
	return l3;
}

void SLTPrint(struct ListNode* phead)
{
	struct ListNode* node = phead;
	while (node)
	{
		printf("%d->", node->val);
		node = node->next;
	}
	printf("NULL\n");
}
int main()
{
	struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	l1->val = 1;
	l1->next= (struct ListNode*)malloc(sizeof(struct ListNode));
	l1->next->val = 4;
	l1->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
	l1->next->next->val = 5;
	l1->next->next->next = NULL;
	struct ListNode* l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	l2->val = 1;
	l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
	l2->next->val = 3;
	l2->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
	l2->next->next->val = 6;
	l2->next->next->next = NULL;
	struct ListNode* l3 = mergeTwoLists(l1, l2);
	SLTPrint(l3);
	return 0;
}